#include <stdio.h> 
#include <stdlib.h>

typedef struct node
{
    int data;
    struct node* next;
}Node;

void output(Node* list)
{
    Node* p = list->next;
    while (p)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

void create(Node** list)
{
    Node* node = (Node*)malloc(sizeof(Node));
    node->next = NULL;
    *list = node;
}

void release(Node** list)
{
    Node* q = NULL;
    Node* p = (*list)->next;

    while (p)
    {
        q = p;
        p = p->next;
        free(q);
    }

    free(*list);
    *list = NULL;
}

void push_back(Node* list, int data)
{
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->next = NULL;

    Node* p = list;
    while (p->next)
        p = p->next;

    p->next = node;
}

void push_back(Node* list, Node* node)
{
    Node* p = list;

    while (p->next)
        p = p->next;
    p->next = node;

    node->next = NULL;
}

Node* pop_back(Node* list)
{
    Node* q = list;
    Node* p = list->next;
    if (p == NULL)
    {
        return NULL;
    }
    else
    {
        while (p->next)
        {
            q = p;
            p = p->next;
        }
        q->next = NULL;

        return p;
    }
}

void move(Node* listFrom, Node* listTo)
{
    Node* p = pop_back(listFrom);
    if (p)
    {
        push_back(listTo, p);
    }
}

void Hanoi(int n, Node* listA, Node* listB, Node* listC)
{
    if (n == 1)
    {
        move(listA, listC);
    }
    else
    {
        Hanoi(n - 1, listA, listC, listB);
        move(listA, listC);
        Hanoi(n - 1, listB, listA, listC);
    }
}

int main()
{
    Node* listA;
    Node* listB;
    Node* listC;

    create(&listA);
    create(&listB);
    create(&listC);


    for (int i = 0; i < 5; i++)
    {
        push_back(listA, 5 - i);
    }
    printf("A: ");
    output(listA);

    Hanoi(5, listA, listB, listC);

    printf("C: ");
    output(listC);

    release(&listA);
    release(&listB);
    release(&listC);

    return 0;
}
